﻿#define _CRT_SECURE_NO_WARNINGS 1

using namespace std;
#include <iostream> 
#include <vector>
#include <queue>
#include <unordered_map>

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
    
};
// 链表 - 两数相加
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
    {
        ListNode* cur1 = l1, * cur2 = l2;
        ListNode* res = new ListNode(-1);
        ListNode* cur = res;
        int carry = 0, x1 = 0, x2 = 0, x = 0;
        while (cur1 || cur2 || carry)
        {
            x1 = cur1 == nullptr ? 0 : cur1->val;
            x2 = cur2 == nullptr ? 0 : cur2->val;
            x = x1 + x2 + carry;

            carry = x / 10;
            x = x % 10;

            cur->next = new ListNode(x);
            cur = cur->next;

            if (cur1)    cur1 = cur1->next;
            if (cur2)    cur2 = cur2->next;
        }
        // if(carry == 1)
        //     cur->next = new ListNode(1);

        ListNode* ans = res->next;
        delete res;

        return ans;
    }
};
// 链表 - 两两交换链表中的结点
class Solution {
public:
    ListNode* swapPairs(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* x = new ListNode(-1);
        ListNode* prev = x;
        prev->next = head;
        ListNode* cur = head, * _next = head->next;
        ListNode* nnext = _next->next;

        while (cur && _next)
        {
            prev->next = _next;
            _next->next = cur;
            cur->next = nnext;

            prev = cur;
            cur = nnext;
            if (cur)     _next = cur->next;
            if (_next)   nnext = _next->next;
        }
        return x->next;
    }
};

// 链表 - 重排链表
class Solution {
public:
    void reorderList(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr || head->next->next == nullptr) return;

        ListNode* fast = head, * slow = head, * prev = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            if (slow != head)
                prev = prev->next;
            slow = slow->next;
        }
        prev->next = nullptr;
        ListNode* a = nullptr, * b = slow, * c = slow->next;
        while (b)
        {
            b->next = a;
            a = b;
            b = c;
            if (c)   c = c->next;
        }
        ListNode* cur1 = head, * cur2 = a;
        ListNode* ret = new ListNode(0);
        ListNode* cur = ret;
        while (cur1)
        {
            cur->next = cur1;
            cur1 = cur1->next;
            cur = cur->next;

            if (cur2)
            {
                cur->next = cur2;
                cur2 = cur2->next;
                cur = cur->next;
            }
        }
        delete ret;
    }
};
// 链表 - 合并k个链表(解法一：优先级队列)
class Solution {
public:
    struct Compare
    {
        bool operator()(const ListNode* x, const ListNode* y)
        {
            return x->val > y->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        // 创建小根堆
        priority_queue<ListNode*, vector<ListNode*>, Compare> pq;

        // 让头节点都进入小根堆
        for (int i = 0; i < lists.size(); i++)
        {
            if (lists[i])
                pq.push(lists[i]);
        }

        ListNode* x = new ListNode(-1);
        ListNode* cur = x;
        while (!pq.empty())
        {
            auto tmp = pq.top();
            pq.pop();
            cur->next = tmp;
            cur = cur->next;
            if (tmp->next)   pq.push(tmp->next);
        }
        return x->next;
    }
};
// 链表 - 合并k个链表(解法二：归并递归)
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        return merge(lists, 0, lists.size() - 1);
    }
    ListNode* merge(vector<ListNode*> lists, int left, int right)
    {
        if (left > right)    return nullptr;
        if (left == right)   return lists[left];

        int mid = (left + right) >> 1;

        // [left, mid][mid + 1, right]
        ListNode* l1 = merge(lists, left, mid);
        ListNode* l2 = merge(lists, mid + 1, right);

        return mergeHelper(l1, l2);
    }
    ListNode* mergeHelper(ListNode* l1, ListNode* l2)
    {
        if (l1 == nullptr)   return l2;
        if (l2 == nullptr)   return l1;

        ListNode* newhead = new ListNode(-1);
        ListNode* cur1 = l1, * cur2 = l2, * cur = newhead;
        while (cur1 && cur2)
        {
            if (cur1->val <= cur2->val)
            {
                cur->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                cur->next = cur2;
                cur2 = cur2->next;
            }
            cur = cur->next;
        }
        if (cur1)
            cur->next = cur1;
        if (cur2)
            cur->next = cur2;
        return newhead->next;
    }
};

// 链表 - K个⼀组翻转链表
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k)
    {
        if (head == nullptr) return nullptr;
        if (head->next == nullptr)   return head;
        int len = 0;
        ListNode* cur = head;
        while (cur)
        {
            len++;
            cur = cur->next;
        }
        cur = head;
        int n = len / k;

        ListNode* x = new ListNode(-1);
        ListNode* prev = x;
        // 重复n次长度为k的链表逆序
        for (int i = 0; i < n; i++)
        {
            ListNode* tmp = cur;
            for (int j = 0; j < k; j++)
            {
                ListNode* _next = cur->next;
                cur->next = prev->next;
                prev->next = cur;
                cur = _next;
            }
            prev = tmp;
        }

        // 把不需要翻转的连接上
        prev->next = cur;

        ListNode* ans = x->next;
        delete x;
        return ans;
    }
};
// 哈希 - 两数之和
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        unordered_map<int, int> hash;//[K, V]->[nums[i], i]
        for (int i = 0; i < nums.size(); i++)
        {
            int x = target - nums[i];
            if (hash.count(x))   return { hash[x], i };
            hash[nums[i]] = i;
        }
        return { -1, -1 };
    }
};
// 哈希 - 判断是否互为字符重排
class Solution {
public:
    bool CheckPermutation(string s1, string s2)
    {
        int hash[26] = { 0 };
        for (auto& e : s1)
            hash[e - 'a']++;
        for (auto& e : s2)
            hash[e - 'a']--;

        for (int i = 0; i < 26; i++)
        {
            if (hash[i] != 0)
                return false;
        }
        return true;
    }
};
// 哈希 - 存在重复元素 I
class Solution {
public:
    bool containsDuplicate(vector<int>& nums)
    {
        unordered_map<int, int> hash;//[nums[i], 出现的次数]
        for (auto& e : nums)
            hash[e]++;
        for (int i = 0; i < nums.size(); i++)
        {
            if (hash[nums[i]] > 1)
                return true;
        }
        return false;
    }
};
// 哈希 - 存在重复元素 II
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash;// [K, V] -> [nums[i], i]
        for (int i = 0; i < nums.size(); i++)
        {
            if (hash.count(nums[i]) && abs(hash[nums[i]] - i) <= k && hash[nums[i]] != i)
                return true;
            hash[nums[i]] = i;
        }
        return false;
    }
};
// 哈希 - 字⺟异位词分组
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs)
    {
        unordered_map<string, vector<string>> hash;
        for (auto& e : strs)
        {
            string tmp = e;
            sort(tmp.begin(), tmp.end());
            hash[tmp].emplace_back(e);
        }

        vector<vector<string>> vv;
        for (auto& e : hash)
        {
            vv.emplace_back(e.second);
        }
        /*auto ret = hash.begin();
        while (ret != hash.end())
        {
            vv.emplace_back(ret->second);
            ++ret;
        }*/
        return vv;
    }
};
// 字符串 - ⼆进制求和
class Solution {
public:
    string addBinary(string a, string b)
    {
        string ret;
        int carry = 0, cur1 = a.size() - 1, cur2 = b.size() - 1;
        while (cur1 >= 0 || cur2 >= 0 || carry)
        {
            if (cur1 >= 0)   carry += a[cur1--] - '0';
            if (cur2 >= 0)   carry += b[cur2--] - '0';

            ret += carry % 2 + '0';
            carry /= 2;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

// 最⻓回⽂⼦串 ?
class Solution {
public:
    string longestPalindrome(string s)
    {
        int len = 0, begin = 0;
        for (int i = 0; i < s.size(); i++)
        {
            // 奇数
            int left = i, right = i;
            while (left >= 0 && right < s.size() && s[left] == s[right])
            {
                left--;
                right++;
            }
            if (right - left - 1 > len)
            {
                len = right - left - 1;
                begin = left + 1;
            }

            // 偶数
            left = i, right = i + 1;
            while (left >= 0 && right < s.size() && s[left] == s[right])
            {
                left--;
                right++;
            }
            if (right - left - 1 > len)
            {
                len = right - left - 1;
                begin = left + 1;
            }
        }
        return s.substr(begin, len);
    }
};
// 最⻓公共前缀
class Solution {
public:
    // 比较全部
    string longestCommonPrefix(vector<string>& strs)
    {
        for (int i = 0; i < strs[0].size(); i++)
        {
            char tmp = strs[0][i];
            for (int j = 1; j < strs.size(); j++)
            {
                if (i == strs[j].size() || tmp != strs[j][i])
                    return strs[0].substr(0, i);
            }
        }
        return strs[0];
    }
};
class Solution {
public:
    // 两两比较
    string longestCommonPrefix(vector<string>& strs)
    {
        string ans = strs[0];
        for (int i = 1; i < strs.size(); i++)
            ans = Compare(ans, strs[i]);
        return ans;
    }
    string Compare(string& ans, string& str)
    {
        string ret;
        for (int i = 0; i < min(ans.size(), str.size()) && ans[i] == str[i]; i++)
        {
            ret += ans[i];
        }
        return ret;
    }
};
// 区间反转链表
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right)
    {
        // 创建头节点
        ListNode* ans = new ListNode(-1);
        ans->next = head;
        ListNode* prev = ans;
        for (int i = 0; i < left - 1; i++)
        {
            prev = prev->next;
        }
        ListNode* cur = prev->next;
        ListNode* _next;
        // 遍历区间
        for (int i = left; i < right; i++)
        {
            _next = cur->next;
            cur->next = _next->next;
            _next->next = prev->next;
            prev->next = _next;
        }
        return ans->next;
    }
};
// 删除字符中的所有相邻重复项 (模拟栈)
class Solution {
public:
    string removeDuplicates(string str)
    {
        string ret;
        for (auto e : str)
        {
            if (ret.size() && e == ret.back())   ret.pop_back();
            else    ret += e;
        }
        return ret;
    }
};
// ⽐较含退格的字符串 (模拟栈)
class Solution {
public:
    bool backspaceCompare(string s, string t)
    {
        return changeStr(s) == changeStr(t);
    }
    string changeStr(string& s)
    {
        string ret;
        for (auto e : s)
        {
            if (e != '#')    ret += e;
            else
            {
                if (ret.size())
                    ret.pop_back();
            }
        }
        return ret;
    }
};
// 基本计算器II （模拟栈）
class Solution {
public:
    int calculate(string s)
    {
        // 数组模拟栈
        vector<int> ret;
        char op = '+';
        int i = 0, n = s.size();
        while (i < n)
        {
            // 是空格就跳过
            if (s[i] == ' ') i++;
            else if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9')
                    // 提取数字
                    tmp = (s[i++] - '0') + tmp * 10;
                // 分类讨论，优先级低的入栈，高的运算
                if (op == '+')   ret.push_back(tmp);
                else if (op == '-')  ret.push_back(-tmp);
                else if (op == '*')  ret.back() *= tmp;
                else    ret.back() /= tmp;
            }
            else
            {
                op = s[i];
                i++;
            }
        }
        int ans = 0;
        // 将ret中的数字相加就是最后结果
        for (auto e : ret)
            ans += e;
        return ans;
    }
};
#include <stack>
// 字符串解码 - 
class Solution {
public:
    string decodeString(string s)
    {
        stack<int> num;
        stack<string> str;
        str.push("");
        int i = 0, n = s.size();
        while (i < n)
        {
            // 当s[i]为数字的时候，提取出数字
            if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (s[i] >= '0' && s[i] <= '9')
                {
                    tmp = tmp * 10 + (s[i] - '0');
                    i++;
                }
                num.push(tmp);  //入数字栈
            }
            // 当s[i]为字符的时候
            else if (s[i] == '[')
            {
                i++;
                string tmp;
                while (s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                str.push(tmp);  // 入字符串栈
            }
            else if (s[i] == ']')
            {
                i++;
                string tmp = str.top();
                str.pop();
                int k = num.top();
                num.pop();
                while (k--)             // 执行字符串复制操作
                    str.top() += tmp;   // 将字符串拼接到字符串栈的栈顶元素中
            }
            else
            {   // 处理其他元素的情况
                string tmp;
                while (i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];    
                    i++;
                }
                str.top() += tmp;
            }
        }
        return str.top();
    }
};
// 验证栈序列 -- 模拟栈
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
    {
        stack<int> st;
        int j = 0;
        for (int i = 0; i < pushed.size(); i++)
        {
            // 让元素入栈，同时检查栈顶元素是否与出栈序列元素相等
            st.push(pushed[i]);
            // 相等就出栈
            while (!st.empty() && st.top() == popped[j])
            {
                st.pop();
                j++;
            }
        }
        // 判断栈是否为空，为空则说明是出栈序列
        return st.empty();
    }
};